package hot;

public class Num85 {
    public static void main(String[] args) {
        Num85 n = new Num85();
        System.out.println(n.maximalRectangle(new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}}));
    }
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        if(n == 0) return 0;
        int m = matrix[0].length;
        int[][] maxim = new int[n][m];
        for(int i = 0; i < m; i++) {
            if(matrix[0][i] == '1') maxim[0][i] = 1;
        }
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < m; j ++) {
                if(matrix[i][j] == '1') maxim[i][j] = maxim[i - 1][j] + 1;
            }
        }
        int ans = 0;
        int wid = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(maxim[i][j] * m <= ans) continue;
                if(maxim[i][j] != 0) {
                    int left = j;
                    int val = maxim[i][j];
                    while(left >= 0 && maxim[i][left] >= val) {
                        wid++;
                        left--;
                    }
                    int right = j + 1;
                    while(right < m && maxim[i][right] >= val) {
                        wid++;
                        right++;
                    }
                    int s = val * wid;
                    if(s > ans) {
                        ans = s;
                    }
                    wid = 0;
                }
            }
        }
        return ans;
    }
}
